//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
//
// 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
// Related Topics 链表 双指针 
// 👍 2060 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * [P19]_删除链表的倒数第 N 个结点
 *
 * @author cjl
 * @date 2022-05-29 20:00:56
 */
public class P19_RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P19_RemoveNthNodeFromEndOfList().new Solution();
        ListNode L5 = new P19_RemoveNthNodeFromEndOfList().new ListNode(5, null);
        ListNode L4 = new P19_RemoveNthNodeFromEndOfList().new ListNode(4, L5);
        ListNode L3 = new P19_RemoveNthNodeFromEndOfList().new ListNode(3, L4);
        ListNode L2 = new P19_RemoveNthNodeFromEndOfList().new ListNode(2, L3);
        ListNode L1 = new P19_RemoveNthNodeFromEndOfList().new ListNode(1, L2);
        ListNode node = solution.removeNthFromEnd(L1, 5);
        while (node != null) {
            System.out.println("args = " + node.val);
            node = node.next;
        }
    }
    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            /**
             * 解题思路：双指针， first 和second 相差n开始顺次遍历，second遍历到最后一个时，first刚好时要删除的节点
             * 注意：一种常用的技巧是添加一个哑节点（dummy node），它的next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
             */
            ListNode dummyNode = new ListNode(); //哑节点
            dummyNode.next = head;
            ListNode first = dummyNode; //
            ListNode second = dummyNode;
            int i = 0;
            while (null != second) {
                second = second.next;
                if (i > n) { //边界一定要细致；
                    first = first.next;
                }
                i++;
            }
            first.next = first.next.next;
            return dummyNode.next;
        }

        /**
         * 解题思路：空间换时间,遍历一遍，使用 Map记录每个ListNode及其序号
         * 一种常用的技巧是添加一个哑节点（dummy node），它的next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
         */
        public ListNode removeNthFromEnd2(ListNode head, int n) {

            Map<Integer, ListNode> map = new HashMap<>();
            ListNode tmpNode = new ListNode();
            tmpNode.next = head;
            ListNode current = tmpNode;
            int i = 0;
            while (null != current) {
                map.put(i, current);
                i++;
                current = current.next;
            }
            ListNode delNode = map.get(map.keySet().size() - n);
            ListNode delPreNode = map.get(map.keySet().size() - n - 1);
            delPreNode.next = delNode.next;
            return tmpNode.next;
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}